package huaweiod.first;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 华为OD机试真题 Java 实现【最差产品奖】【2022.11 Q4 新题】
 */
public class A_2023_43_WorstProduct {

    public static void main(String[] args) {
        int window = 3;
        String str = "12,3,8,6,5";
        List<Integer> collect = Arrays.stream(str.split(",")).map(Integer::parseInt).collect(Collectors.toList());
        if (collect.size() < window) {
            return;
        }
        Deque<Integer> dq = new LinkedList<>();
        StringJoiner sj = new StringJoiner(",");
        for (int i = 0; i < collect.size(); i++) {
            if (i >= window) {
                sj.add(String.valueOf(dq.peekFirst()));
                if (collect.get(i - window).equals(dq.peekFirst())) {
                    dq.removeFirst();
                }
            }
            while (!dq.isEmpty() && dq.peekLast() > collect.get(i)) {
                dq.pollLast();
            }
            dq.addLast(collect.get(i));
        }
        sj.add(String.valueOf(dq.peekFirst()));
        System.out.println(sj);
    }

}
